from functools import cache
import copy
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        length = len(s)
        wordset = set(wordDict)
        @cache
        def search(i):
            return_list = []
            for j in range(i + 1, length + 1):
                if s[i: j] in wordset:
                    if j == length:
                        return_list.append(s[i: j])
                    else:
                        hou_xu = search(j)
                        for item in hou_xu:
                            return_list.append(s[i:j] + ' ' + item)
            return return_list
        return search(0)



data = Solution()
s = "catsandog"
wordDict = ["cats","dog","sand","and","cat"]
print(data.wordBreak(s, wordDict))
s = "catsanddog"
wordDict = ["cat","cats","and","sand","dog"]
print(data.wordBreak(s, wordDict))
s = "pineapplepenapple"
wordDict = ["apple","pen","applepen","pine","pineapple"]
print(data.wordBreak(s, wordDict))